#include <stdio.h>  
#include <stdlib.h>  
  
/* 定义单链表节点结构体 */  
struct ListNode {  
    int val;  
    struct ListNode *next;  
};  
  
/* 定义函数用于创建新节点 */  
struct ListNode* createNode(int val) {  
    struct ListNode *newNode = (struct ListNode*)malloc(sizeof(struct ListNode));  
    newNode->val = val;  
    newNode->next = NULL;  
    return newNode;  
}  
  
/* 定义函数用于将单链表按照给定的首结点值x分割成两部分 */  
void splitList(struct ListNode *head, int x) {  
    /* 定义两个指针，分别指向链表的头部和尾部 */  
    struct ListNode *head1 = NULL, *tail1 = NULL;  
    struct ListNode *head2 = NULL, *tail2 = NULL;  
    /* 遍历链表，将节点插入到相应的链表中 */  
    struct ListNode *current = head;  
    while (current != NULL) {  
        if (current->val < x) {  
            if (head1 == NULL) {  
                head1 = current;  
                tail1 = current;  
            } else {  
                tail1->next = current;  
                tail1 = current;  
            }  
        } else {  
            if (head2 == NULL) {  
                head2 = current;  
                tail2 = current;  
            } else {  
                tail2->next = current;  
                tail2 = current;  
            }  
        }  
        current = current->next;  
    }  
    /* 将两个链表连接起来 */  
    if (head1 != NULL) {  
        tail1->next = head2;  
    } else {  
        head = head2;  
    }  
}  
  
/* 定义函数用于输出单链表中的所有元素 */  
void printList(struct ListNode *head) {  
    struct ListNode *current = head;  
    while (current != NULL) {  
        printf("%d ", current->val);  
        current = current->next;  
    }  
    printf("\n");  
}  
  
/* 测试程序 */  
int main() {  
    /* 创建单链表：1 < 3 < 5 < 7 < 9 */  
    struct ListNode *head = createNode(1);  
    head->next = createNode(3);  
    head->next->next = createNode(5);  
    head->next->next->next = createNode(7);  
    head->next->next->next->next = createNode(9);  
    /* 将单链表按照首结点值4分割成两部分 */  
    splitList(head, 4);  
    /* 输出分割后的单链表 */  
    printList(head);  /* 输出：1 3 5 7 */  
    struct ListNode *current = head->next->next->next->next;  /* 指向分割后的第二个链表的头部 */  
    printList(current);  /* 输出：9 */  
    return 0;  
}

